package LRU;

import java.util.HashMap;
import java.util.Map;

/**
 * LRU缓存实现：单链表 + 哈希表（方案B）
 * 时间复杂度：get/put均为O(n)（删除节点需遍历前驱）
 * @param <K> 键类型
 * @param <V> 值类型
 */
public class LRUWithSingleLinkedList<K, V> {
    // 缓存容量
    private int capacity;
    // 当前缓存数据量
    private int size;
    // 单链表头节点（最近访问）
    private SingleLinkedNode<K, V> head;
    // 哈希表：key -> 单链表节点（O(1)定位）
    private Map<K, SingleLinkedNode<K, V>> cacheMap;

    // 初始化缓存
    public void init(int capacity) {
        if (capacity <= 0) {
            throw new IllegalArgumentException("缓存容量必须大于0");
        }
        this.capacity = capacity;
        this.size = 0;
        // 初始化头节点（哨兵节点）
        this.head = new SingleLinkedNode<>();
        this.cacheMap = new HashMap<>(capacity);
    }

    /**
     * 根据key查询value
     * @param key 键
     * @return 存在则返回value，否则返回null
     */
    public V get(K key) {
        if (key == null) {
            throw new NullPointerException("key不能为null");
        }
        // 1. 哈希表定位节点
        SingleLinkedNode<K, V> node = cacheMap.get(key);
        if (node == null) {
            return null;
        }
        // 2. 找到节点的前驱（单链表需遍历）
        SingleLinkedNode<K, V> prev = findPrev(node);
        if (prev != null) {
            // 2.1 移除节点（前驱的next指向节点的next）
            prev.setNext(node.getNext());
            // 2.2 将节点插入头部
            node.setNext(head.getNext());
            head.setNext(node);
        }
        return node.getValue();
    }

    /**
     * 插入或更新键值对
     * @param key 键
     * @param value 值
     */
    public void put(K key, V value) {
        if (key == null || value == null) {
            throw new NullPointerException("key或value不能为null");
        }
        // 1. 检查key是否已存在
        SingleLinkedNode<K, V> node = cacheMap.get(key);
        if (node != null) {
            // 1.1 存在：更新value并移至头部
            node.setValue(value);
            SingleLinkedNode<K, V> prev = findPrev(node);
            if (prev != null) {
                prev.setNext(node.getNext());
                node.setNext(head.getNext());
                head.setNext(node);
            }
            return;
        }
        // 2. 不存在：新建节点
        SingleLinkedNode<K, V> newNode = new SingleLinkedNode<>(key, value);
        // 2.1 插入哈希表
        cacheMap.put(key, newNode);
        // 2.2 插入链表头部
        newNode.setNext(head.getNext());
        head.setNext(newNode);
        size++;
        // 2.3 若缓存满，淘汰尾部节点
        if (size > capacity) {
            SingleLinkedNode<K, V> removedNode = removeTail();
            // 从哈希表中移除
            cacheMap.remove(removedNode.getKey());
            size--;
        }
    }

    // -------------------------- 单链表辅助方法 --------------------------
    /**
     * 找到指定节点的前驱节点（单链表核心痛点：需遍历）
     */
    private SingleLinkedNode<K, V> findPrev(SingleLinkedNode<K, V> target) {
        SingleLinkedNode<K, V> prev = head;
        while (prev.getNext() != null) {
            if (prev.getNext() == target) {
                return prev;
            }
            prev = prev.getNext();
        }
        return null; // 未找到（理论上不会出现，因target来自哈希表）
    }

    /**
     * 移除尾部节点（最少访问位置，需遍历至倒数第二个节点）
     */
    private SingleLinkedNode<K, V> removeTail() {
        SingleLinkedNode<K, V> prev = head;
        // 遍历至倒数第二个节点（prev.next.next == null）
        while (prev.getNext() != null && prev.getNext().getNext() != null) {
            prev = prev.getNext();
        }
        // 尾部节点是prev.next
        SingleLinkedNode<K, V> removedNode = prev.getNext();
        prev.setNext(null); // 删除尾部节点
        return removedNode;
    }

    // -------------------------- 状态查询方法 --------------------------
    public int size() {
        return size;
    }

    public boolean isFull() {
        return size == capacity;
    }
}